package cn.fxzhang.leetcode.no02;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 264. 丑数 II
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 提示：
 * 1 <= n <= 1690
 *
 * 类型：枚举
 * 题解：在当前丑数的基础上，拓展出新的丑数
 * 时间复杂度：O(N), N为第n个丑数的大小
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 58 ms, 击败了20.56%
 * 内存消耗: 38.1 MB, 击败了15.24%
 *
 * 【中等】通过次数59,462提交次数105,815
 * todo 速度较慢，可试下最小堆和DP
 * @author 张晓帆
 * @date 2021/4/11
 */
public class P0264_Ugly_Number_Ii {

    public int nthUglyNumber(int n) {
        long[] nums = new long[n];
        nums[0] = 1;
        int start=0;
        int end=0;
        // 每一层的最大值
        long top = 1;
        // 用于去重
        Set<Long> set = new HashSet<>();
        set.add(1L);
        while (end<n-1){
            top = top*5;
            // 新的一层
            long[] a = new long[n*2+100];
            int len = 0;
            for (int i=start; i<=end; i++){
                long x = nums[i];
                long z = x*2;
                while (z<=top){
                    if (set.add(z)) {
                        a[len++] = z;
                    }
                    z *= 2;
                }
                z = x*3;
                while (z<=top){
                    if (set.add(z)) {
                        a[len++] = z;
                    }
                    z *= 3;
                }
                z = x*5;
                while (z<=top){
                    if (set.add(z)) {
                        a[len++] = z;
                    }
                    z = z*5;
                }
            }
            Arrays.sort(a,0, len);
            int j = end;
            for (int i=0; i<len && j<n-1; i++){
                nums[++j] = a[i];
            }
            start = end+1;
            end = end+len;
        }
        return (int)nums[n-1];
    }
}
